package queenChessProblem;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;

import utils.RandomGenerator;
import genetic_algorithm.Chromosome;
import genetic_algorithm.Crossover;
import genetic_algorithm.Mutation;

/**
 * Implementation of the crossover phase for the genetic algorithm
 * to solves the queens problem
 */
public class QueensCrossover implements Crossover {

	public static final int SINGLE_POINT = 0; // single point crossover
	public static final int DOUBLE_POINT = 1; // double point crossover
	public static final int UNIFORM = 2; // uniform crossover
	public static final int SMART_MIX = 3;
	private int mode; // crossover mode

	/**
	 * Constructor- creates a new object implementing crossover phase for the
	 * queens problem. Crossover is performed according to given crossover mode:
	 * single point, double point, uniform or smart
	 * @param mode mode for the crossover
	 */
	public QueensCrossover(int mode) {
		// set crossover mode
		this.mode = mode;
	}

	/**
	 * Gets a pair of parent chromosomes. In chance of crossover-rate, mates
	 * parents (according to the mode which was specified during the
	 * initialization) and mutates them in chance of mutation-rate. If crossover
	 * is not performed, parents are not changed and returned as they are
	 */
	@Override
	public Entry<Chromosome, Chromosome> mate(
			Entry<Chromosome, Chromosome> parents, double crossoverRate,
			Mutation mutator, double mutationRate) {

		// skip crossover in chance of crossover-rate
		if ((RandomGenerator.nextInt(1000) / 1000.0) > crossoverRate) {
			return parents;
		}

		// perform crossover according to selected mode
		List<Chromosome> offsprings = null;
		switch (mode) {
		case SINGLE_POINT: {
			offsprings = singlePoint(parents.getKey(), parents.getValue());
			break;
		}
		case DOUBLE_POINT: {
			offsprings = doublePoint(parents.getKey(), parents.getValue());
			break;
		}
		case UNIFORM: {
			offsprings = uniform(parents.getKey(), parents.getValue());
			break;
		}
		case SMART_MIX: {
			offsprings = smartMix(parents.getKey(), parents.getValue());
			break;
		}

		default:
			break;
		}

		// mutate the offsprings
		mutator.mutate(offsprings, mutationRate);

		// return resulting offsprings
		return new AbstractMap.SimpleEntry<Chromosome, Chromosome>(
				offsprings.get(0), offsprings.get(1));
	}

	/**
	 * Performs crossover on given parent chromosomes in a single-point manner:
	 * randomly picks an index in the parents' list values; generates first
	 * offspring by concatenating father's prefix with mother's postfix;
	 * generates second offspring by concatenating mother's prefix with father's
	 * postfix
	 * @param father first parent chromosome
	 * @param mother second parent chromosome
	 * @return list containing offsprings chromosmes
	 */
	private List<Chromosome> singlePoint(Chromosome father, Chromosome mother) {

		// initialize values list for offspring chromosomes
		List<Object> firstOffspringVals = new LinkedList<Object>();
		List<Object> secondOffspringVals = new LinkedList<Object>();

		// randomly choose split index
		int numValues = father.getAllValues().size();
		int splitIndex = RandomGenerator.nextInt(numValues);

		// extract prefix and postfix of chromosomes' values // TODO CHECK IF SHOULD COPY SUB LISTS ELEMENTS
		List<Object> fatherPrefix = father.getAllValues().subList(0, splitIndex);
		List<Object> fatherPostfix = father.getAllValues().subList(splitIndex,numValues);
		List<Object> motherPrefix = mother.getAllValues().subList(0, splitIndex);
		List<Object> motherPostfix = mother.getAllValues().subList(splitIndex,numValues);

		// concatenate father's prefix with mother's postfix
		firstOffspringVals.addAll(fatherPrefix);
		firstOffspringVals.addAll(motherPostfix);

		// concatenate mother's prefix with father's postfix
		secondOffspringVals.addAll(motherPrefix);
		secondOffspringVals.addAll(fatherPostfix);

		// generate chromosomes out of offsprings values
		QueensChromosome firstOffspring = new QueensChromosome(firstOffspringVals);
		QueensChromosome secondOffspring = new QueensChromosome(secondOffspringVals);

		// return resulting chromosomes
		List<Chromosome> offsprings = new LinkedList<Chromosome>();
		offsprings.add(firstOffspring);
		offsprings.add(secondOffspring);
		return offsprings;
	}

	/**
	 * Performs crossover on given parent chromosomes in a double-point manner:
	 * randomly picks two indices in the parents' list values; generates first
	 * offspring by concatenating father's first sublist with mother's second
	 * sublist and father's third sublist; generates second offspring by
	 * concatenating mother's first sublist with father's second sublist and
	 * mother's third sublist 
	 * @param father first parent chromosome
	 * @param mother second parent chromosome
	 * @return list containing offsprings chromosmes
	 */
	private List<Chromosome> doublePoint(Chromosome father, Chromosome mother) {

		// split and merge parents until valid offsprings are generated
		List<Object> firstOffspringVals = new LinkedList<Object>();
		List<Object> secondOffspringVals = new LinkedList<Object>();

		// randomly choose split indices
		int numValues = father.getAllValues().size();
		int firstSplit = RandomGenerator.nextInt(numValues - 1);
		int secondSplit = RandomGenerator.nextInt(numValues - firstSplit)
				+ firstSplit;

		// extract sublists of each chromosome's values
		List<Object> fatherFirst = father.getAllValues().subList(0,firstSplit);
		List<Object> fatherSecond = father.getAllValues().subList(firstSplit, secondSplit);
		List<Object> fatherThird = father.getAllValues().subList(secondSplit, numValues);
		List<Object> motherFirst = mother.getAllValues().subList(0,firstSplit);
		List<Object> motherSecond = mother.getAllValues().subList(firstSplit, secondSplit);
		List<Object> motherThird = mother.getAllValues().subList(secondSplit, numValues);

		// concatenate father and mother's sublists alternately
		firstOffspringVals.addAll(fatherFirst);
		firstOffspringVals.addAll(motherSecond);
		firstOffspringVals.addAll(fatherThird);
		secondOffspringVals.addAll(motherFirst);
		secondOffspringVals.addAll(fatherSecond);
		secondOffspringVals.addAll(motherThird);

		// generate chromosomes out of offsprings values
		QueensChromosome firstOffspring = new QueensChromosome(
				firstOffspringVals);
		QueensChromosome secondOffspring = new QueensChromosome(
				secondOffspringVals);

		// return resulting chromosomes
		List<Chromosome> offsprings = new LinkedList<Chromosome>();
		offsprings.add(firstOffspring);
		offsprings.add(secondOffspring);
		return offsprings;
	}

	// TODO SHOULD DELTE?
	private List<Chromosome> uniform(Chromosome father, Chromosome mother) {
		
		// initialize values list for offspring chromosomes
		List<Object> firstOffspringVals = new LinkedList<Object>();
		List<Object> secondOffspringVals = new LinkedList<Object>();

		// fill values
		int numValues = father.getAllValues().size();
		int isFather; // indicates if choosing from father the current value for first offspring
		for (int i = 0 ; i < numValues ; ++i) {
			
			// choose randomly the parent to inherit its current value
			isFather = RandomGenerator.nextInt(2);
			if (isFather == 0) {
				firstOffspringVals.add(father.getValue(i));
				secondOffspringVals.add(mother.getValue(i));
			} else {
				firstOffspringVals.add(mother.getValue(i));
				secondOffspringVals.add(father.getValue(i));
			}
		}
		
		// generate chromosomes out of offsprings values
		QueensChromosome firstOffspring = new QueensChromosome(firstOffspringVals);
		QueensChromosome secondOffspring = new QueensChromosome(secondOffspringVals);

		// return resulting chromosomes
		List<Chromosome> offsprings = new LinkedList<Chromosome>();
		offsprings.add(firstOffspring);
		offsprings.add(secondOffspring);
		return offsprings;
	}
	
	// TODO SHOULD DELETE?
	private List<Chromosome> smartMix(Chromosome father, Chromosome mother) {

		Entry<int[], int[]> fatherSubs = findBestSubList(father);
		Entry<int[], int[]> motherSubs = findBestSubList(mother);

		List<Object> child1 = new ArrayList<Object>();
		for (int i = 0; i < 8; i++) {
			child1.add(new Integer(-1));
		}
		for (Integer i : fatherSubs.getKey()) {
			child1.set(i, father.getAllValues().get(i));
		}
		for (int i = 0; i < 8; i++) {
			if ((Integer) child1.get(i) == -1)
				child1.set(i, mother.getAllValues().get(i));
		}

		List<Object> child2 = new ArrayList<Object>();
		for (int i = 0; i < 8; i++) {
			child2.add(new Integer(-1));
		}
		for (Integer i : motherSubs.getKey()) {
			child2.set(2, father.getAllValues().get(i));
//			child2.set(i, father.getAllValues().get(i));
		}
		for (int i = 0; i < 8; i++) {
			if ((Integer) child1.get(i) == -1)
//			if ((Integer) child2.get(i) == -1)
				child2.set(i, mother.getAllValues().get(i));
		}

		// generate chromosomes out of offsprings values
		QueensChromosome firstChrom = new QueensChromosome(child1);
		QueensChromosome secondChrom = new QueensChromosome(child2);

		// return resulting chromosomes
		List<Chromosome> result = new LinkedList<Chromosome>();
		result.add(firstChrom);
		result.add(secondChrom);
		return result;

	}

	private Entry<int[], int[]> findBestSubList(Chromosome chrom) {
		
		List<Object> positions = chrom.getAllValues();
		int size = positions.size();
		int firstFit = 0;
		int secondFit = 0;
		int[] firstResult = null;
		int[] secondResult = null;
		
		for (int i = 0; i < size; i++) {
			for (int j = i + 1; j < size; j++) {
				for (int k = j + 1; k < size; k++) {
					for (int l = k + 1; l < size; l++) {
						List<Object> tempSubList = new LinkedList<Object>();
						tempSubList.add(positions.get(i));
						tempSubList.add(positions.get(j));
						tempSubList.add(positions.get(k));
						tempSubList.add(positions.get(l));
						int tempFit = getFitness(tempSubList);
						if (tempFit > firstFit) {
							secondResult = firstResult;
							firstResult = new int[] { i, j, k, l };
							secondFit = firstFit;
							firstFit = tempFit;
						} else if (tempFit > secondFit) {
							secondResult = new int[] { i, j, k, l };
							secondFit = tempFit;
						}
					}
				}
			}
		}
		return new AbstractMap.SimpleEntry<int[], int[]>(firstResult,
				secondResult);
	}

	private int getFitness(List<Object> pList) {
		int f = 0;
		int size = pList.size();
		int x1, x2, y1, y2;
		for (int i = 0; i < size; ++i) {
			for (int j = 0; j < size; ++j) {
				if (i == j)
					continue;
				x1 = i;
				y1 = (Integer) pList.get(i);
				x2 = j;
				y2 = (Integer) pList.get(j);

				if (y1 == y2 || Math.abs((x2 - x1)) == Math.abs((y2 - y1))) {
					++f;
				}
			}
		}
		return f;
	}

}